/*.	dynamic programing*/
#ifndef _DP_
#define _DP_

#include <algorithm>
#include <array>
#include <cmath>
#include <unordered_map>
#include <vector>
using namespace std;

#define MOOD int( 1e9 + 7 )
class DP {

public:
    DP( /* args */ ) {}
    ~DP() {}

    /*剑指 Offer 10- II. 青蛙跳台阶问题 : 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。*/
    // 递归
    int numWays( int n ) {
        if ( n < 0 ) {
            exit( -1 );
        }

        if ( m_hashMap.count( n ) == 1 ) {
            return m_hashMap[ n ] % MOOD;
        }

        if ( n <= 1 ) {
            m_hashMap.insert( std::make_pair< int, int >( 1, 1 ) );
            m_hashMap.insert( std::make_pair< int, int >( 0, 1 ) );
            return 1;
        }

        if ( n == 2 ) {
            m_hashMap.insert( std::make_pair< int, int >( 2, 2 ) );
            return 2;
        }

        m_hashMap.insert( std::make_pair< int, int >( int( n ), int( ( numWays( n - 1 ) + numWays( n - 2 ) ) % MOOD ) ) );

        return m_hashMap[ n ];
    }

    // DP
    int numWays2( int n ) {
        if ( n < 0 ) {
            exit( -1 );
        }

        if ( n <= 1 ) {
            return 1;
        }

        if ( n == 2 ) {
            return 2;
        }

        int result1 = 1;
        int result2 = 2;
        int result;
        for ( int i = 3; i <= n; i++ ) {
            result = result1 + result2;

            result1 = result2 % MOOD;
            result2 = result % MOOD;
        }

        return result % MOOD;
    }

    /* 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。
     * 请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？*/
    int cuttingRope( int n ) {
        if ( n <= 3 ) {
            return n - 1;
        }
        vector< int > dp( n + 1 );
        dp[ 1 ] = 1;

        for ( int i = 2; i <= n; i++ ) {
            int max = INT16_MIN;
            // calculate dp[i]
            for ( int j = 1; j < i; j++ ) {
                int x = dp[ j ] * ( i - j );
                int y = j * ( i - j );
                int r = std::max( x, y );
                max   = std::max( max, r );
            }
            dp[ i ] = max;
            // 优化
            // dp[ i ] = std::max( std::max( 2 * ( i - 2 ), 2 * dp[ i - 2 ] ), std::max( 3 * ( i - 3 ), 3 * dp[ i - 3 ] ) );
        }
        return dp[ n ];
    }
    // 数学推导：算术几何均值不等式
    int cuttingRope2( int n ) {
        if ( n <= 3 ) {
            return n - 1;
        }

        int x = n % 3;
        int a = n / 3;
        switch ( x ) {
        case 1:
            return pow( 3, a - 1 ) * 4;
        case 2:
            return pow( 3, a ) * 2;
        default:
            return pow( 3, a );
        }
    }
    // 循环求余 (x^a)%p = ((x^a-1 %p)*x)%p
    int remainder( int x, int a, int p ) {
        int rem = 1;
        for ( int i = 0; i < a; i++ ) {
            rem = ( rem * x ) % p;
        }
        return rem;
    }

    // 快速幂求余(x^a)%p= ((x^2 % p)^0.5a) % p
    int remainder2( int x, int a, int p ) {
        int rem = 1;
        return rem;
    }

    int cuttingRope3( int n ) {
        if ( n <= 3 ) {
            return n - 1;
        }
        int mood = 1e9 + 7;
        int x    = n % 3;
        int a    = n / 3;
        int ans  = 0;

        switch ( x ) {
        case 1:
            ans = int( pow( 3, a - 1 ) * 4 ) % mood;
            break;
        case 2:
            ans = int( ( pow( 3, a ) ) * 2 ) % mood;
            break;
        default:
            ans = int( pow( 3, a ) ) % mood;
            break;
        }
        return ans;
    }
    /* 斐波那契数列 */
    int fib( int n ) {
        if ( n == 0 )
            return 0;
        if ( n == 1 )
            return 1;
        int mood = 1e9 + 7;

        vector< int > dp( n + 1 );
        dp[ 0 ] = 0;
        dp[ 1 ] = 1;

        for ( int i = 2; i <= n; i++ ) {
            dp[ i ] = ( ( dp[ i - 1 ] % mood ) + ( dp[ i - 2 ] % mood ) ) % mood;
        }

        return dp[ n ];
    }

    /* 剑指 Offer 47. 礼物的最大价值
     * 在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于0）。
     * 你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
     * f(i,j)=max[f(i,j−1),f(i−1,j)]+grid(i,j)
     */
    int maxValue( vector< vector< int > >& grid ) {

        if ( grid.empty() ) {
            return 0;
        }

        int m = grid.size();
        int n = grid[ 0 ].size();

        vector< vector< int > > dp( m, vector< int >( n, 0 ) );

        dp[ 0 ][ 0 ] = grid[ 0 ][ 0 ];

        for ( int i = 0; i < m; i++ ) {
            for ( int j = 0; j < n; j++ ) {
                if ( i == 0 && j == 0 ) {
                    continue;
                }
                else if ( i == 0 ) {
                    dp[ i ][ j ] = dp[ i ][ j - 1 ] + grid[ i ][ j ];
                }
                else if ( j == 0 ) {
                    dp[ i ][ j ] = dp[ i - 1 ][ j ] + grid[ i ][ j ];
                }
                else {
                    // from up or left
                    dp[ i ][ j ] = max( dp[ i - 1 ][ j ], dp[ i ][ j - 1 ] ) + grid[ i ][ j ];
                }
            }
        }

        return dp[ m - 1 ][ n - 1 ];
    }

    /* 剑指 Offer 63. 股票的最大利润 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
     *  dp[i] = max(dp(i-1), price(i) - min(price(0)...price(i-1)) )
     */
    int maxProfit( vector< int >& prices ) {
        int len = prices.size();
        if ( len <= 1 ) {
            return 0;
        }
        int dp = 0;
        int dpn;
        int nMIN = INT16_MAX;
        for ( int i = 0; i < len; i++ ) {
            nMIN = std::min( prices[ i ], nMIN );
            dpn  = std::max( dp, prices[ i ] - nMIN );
            dp   = dpn;
        }

        return dpn;
    }

    int nthUglyNumber( int n ) {
        vector< long > dp( n + 1, INT32_MAX );
        dp[ 1 ] = 1;

        int l = 1, m = 1, k = 1;

        for ( int i = 2; i <= n; i++ ) {

            int a = dp[ l ] * 2;
            int b = dp[ m ] * 3;
            int c = dp[ k ] * 5;

            dp[ i ] = ( a < b ) ? ( ( a < c ) ? a : c ) : ( ( b < c ) ? b : c );

            if ( dp[ i ] == a ) {
                l++;
            }
            if ( dp[ i ] == b ) {
                m++;
            }
            if ( dp[ i ] == c ) {
                k++;
            }
        }
        return dp[ n ];
    }

    // 72. 编辑距离
    int minDistance( string word1, string word2 ) {

        int len1 = word1.size(), len2 = word2.size();

        vector< vector< int > > dp( len1 + 1, vector< int >( len2 + 1 ) );

        for ( int i = 0; i <= len1; i++ ) {
            dp[ i ][ 0 ] = i;
        }
        for ( int j = 0; j <= len2; j++ ) {
            dp[ 0 ][ j ] = j;
        }

        for ( int i = 1; i <= len1; i++ ) {
            for ( int j = 1; j <= len2; j++ ) {
                if ( word1[ i - 1 ] == word2[ j - 1 ] ) {
                    dp[ i ][ j ] = dp[ i - 1 ][ j - 1 ];
                }
                else {
                    dp[ i ][ j ] = std::min( dp[ i - 1 ][ j - 1 ], std::min( dp[ i ][ j - 1 ], dp[ i - 1 ][ j ] ) ) + 1;
                }
            }
        }
        return dp[ len1 ][ len2 ];
    }
    // 剑指 Offer 62. 圆圈中最后剩下的数字 /约瑟夫环 / 丢手绢
    int lastRemaining( int n, int m ) {
        /*  n =5 , m = 3
            0 1 2 3 4
            0 1 * 3 4 -> 3 号位为第一人 3 4 0 1
                                       0 1 2 3 (i +m)%n
        */
        int pos = 0;
        for ( size_t i = 2; i <= n; i++ ) {
            pos = ( pos + m ) % i;
        }

        return pos;
    }

    // 121. 买卖股票的最佳时机
    int maxProfit( vector< int >& prices ) {
        vector< int > dp( prices.size() + 1, 0 );
        int           minCost = INT32_MAX;

        for ( int i = 1; i <= prices.size(); i++ ) {

            minCost = min( minCost, prices[ i - 1 ] );

            dp[ i ] = max( prices[ i - 1 ] - minCost, dp[ i - 1 ] );
        }

        return dp.back() > 0 ? dp.back() : 0;
    }

    // 剑指 Offer 60. n个骰子的点数
    vector< double > dicesProbability( int n ) {

        vector< int > dp1;
        vector< int > dp2;

        for ( int i = 0; i < 6; i++ ) {
            dp1.push_back( 1 );
            dp2.push_back( 1 );
        }

        for ( size_t i = 2; i <= n; i++ ) {
            dp2.clear();
            dp2.resize( i * 6 - i + 1, 0 );
            for ( size_t j = i; j <= n * 6; j++ ) {
                for ( int k = i - 1; k < j; k++ ) {
                    if ( k - i + 1 >= dp1.size() || j - k > 6 ) {
                        continue;
                    }
                    dp2[ j - i ] += dp1[ k - i + 1 ];
                }
            }
            dp1 = dp2;
        }

        size_t           len = dp2.size();
        vector< double > res( len );
        double           a = pow( 6, n );
        for ( int i = 0; i < len; i++ ) {
            res[ i ] = dp2[ i ] / a;
        }

        return res;
    }

    int lengthOfLIS( const vector< int >& nums ) {
        if ( nums.empty() ) {
            return 0;
        }

        int len = nums.size();

        vector< int > dp( len, 1 );

        for ( int i = 1; i < len; i++ ) {
            for ( int j = 0; j < i; j++ ) {
                if ( nums[ i ] > nums[ j ] ) {
                    dp[ i ] = max( dp[ j ] + 1, dp[ i ] );
                }
            }
        }
        return *max_element( dp.begin(), dp.end() );
    }

private:
    std::unordered_map< int, int > m_hashMap;
};

#endif /*_DP_*/